Today, for a public key cryptosystem, a Rivest Shamir Adleman (RSA) system is mainly used, which utilizes modular exponentiation (arithmetic on a finite field GF(p), where GF(p) is a set of remainders when an integer is divided by a prime number p). In the public key cryptosystem, the longer the key length (bit number) becomes, the more security is enhanced. However, in the RSA system, the key length necessary for adequate practical security has increased from 512 bits to 1024 bits and to 2048 bits, so that increase in operation time and hardware resources has become a problem. On the contrary, in a public key cryptosystem using elliptic curve cryptography (hereinafter, referred to as an elliptic curve cryptosystem), arithmetic of 160 or 224 bits can ensure the security equivalent to the RSA system with a key length of 1024 or 2048 bits.
The basic arithmetic in the elliptic curve cryptography is broadly classified into arithmetic based on GF(p), same as that of the RSA cryptography, and arithmetic based on an extension field GF(2n) of GF(2). The arithmetic over GF(2n) is based on exclusive OR (XOR) and has no carry generated in addition. Therefore, the arithmetic over GF(2n) is faster compared to the arithmetic over GF(p) by modular arithmetic of integers. However, in the elliptic curve cryptosystem on GF(2n), modular multiplication over GF(p) is also necessary in order to support signature by an elliptic curve digital signature algorithm (EC-DSA), which is one of the most important algorithms (for example, see Robert J. McEliece, “The Theory of Information and Coding,” Cambridge University Press, 2002).
As an algorithm performing modular multiplication at high speed, there is Montgomery multiplication (for example, see Johann Groszschaedl, “A Bit-Serial United Multiplier Architecture for Finite Fields GF(p) and GF(2m),” C. K. Koc, D. Naccache, and C. Paar (Eds.): CHES 2001, LNCS 2162, p. 202-219, 2001. Springer-Verlag Berlin Heidelberg 2001). The algorithm was initially for GF(p) and based on adders, but the algorithm today is extended to an algorithm using multipliers or arithmetic over GF(2n).
As described above, in the case where the public key cryptography is realized by the elliptic curve cryptography, it is required to perform the arithmetic over GF(p) and arithmetic over GF(2n). Accordingly, the cipher circuit needs a multiplier performing the arithmetic over GF(p) and a multiplier performing the arithmetic over GF(2n).
Herein, in the case of a circuit using multipliers of eight bits or so, even if the circuit is constituted in such a manner that both of the multipliers performing the arithmetic over GF(p) and performing the arithmetic over GF(2n) are mounted and switched by a selector, circuit size is less affected. However, in the case of using a multiplier of 32 or 64 bits for higher speed, the number of gates of the multiplier is increased by the order of the square of the increased bit numbers, and the numbers of selectors and wires are increased. Accordingly, when both of the multipliers performing the arithmetic over GF(p) and performing the arithmetic over GF(2n) are mounted, the increase in circuit size is not negligible.
Therefore, in the case of the cipher circuit performing arithmetic of numbers of 160 or 1024 bits handled in the public key cryptography, for miniaturization of a device with the cipher circuit mounted thereon or the cipher circuit itself, it is not preferred to separately mount the multipliers performing the arithmetic over GF(p) and performing the arithmetic over GF(2n).
In the Montgomery multiplication or the elliptic curve cryptography, algorithms of the arithmetic over GF(p) and the arithmetic over GF(2n) are substantially the same. Accordingly, when the arithmetic is implemented by circuits, data paths are mostly sharable without change except a multiplication core itself. The above-referenced J. Groszschaedl article discloses a multiplier sharable by the arithmetic over GF(p) and GF(2n).
However, such a conventional multiplier is a serial multiplier, which calculates a product by repeatedly using an adder as many times as the number of bits. In the arithmetic over GF(2n), the conventional multiplier simply disables carries. In order to perform integer multiplication with the serial multiplier, it is necessary that the carry is propagated for each cycle from the least significant bit (LSB) to the most significant bit (MSB) or an intermediate result is retained in a register of a size twice the number of bits while remaining as a redundant binary number. Accordingly, it is difficult to speed up arithmetic, and for speeding up, the circuit size should be considerably increased.
Moreover, as previously described, the public key cryptography handles numbers of 160 or 1024 bits, and the cipher circuit thereof uses a very long adder for speeding up. Therefore, in order to transfer data at high speed, a bus width needs to be extended to the bit length of the adder, thus increasing a chip size physically. Moreover, it is almost impossible to generate a physical ASIC (application specific integrated circuit) chip image that has a bus with two inputs of 1024 bits and an output of 1024 bits by using an automatic place-and-route tool. It usually requires a complicated work such as custom layout by hand. On the other hand, if the bus width is not extended, it is necessary to control the adder to wait for data as objects of arithmetic to be collected at the time of execution of the processing, thus lowering the performance.
Hereinabove, the multiplier circuit used for the cipher circuit in the public key cryptography has been discussed. The same holds true of not only cryptography but also various applications that the coding theory is applied to, the applications requiring the arithmetic over GF(p) and the arithmetic over GF(2n). Examples of another application that the coding theory is applied to include an error correcting circuit by an error correcting code (for example, see Ian Blake, Gadiel Seroussi, and Nigel Smart, “Elliptic Curve Cryptography” Cambridge University Press, 1999; and Richard E. Blahut, “Theory and Practice of Error Control Codes,” Addison-Wesley Publishing Company, 1984).